In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Hej, ludzie! Cuda w tej budzie! Chyba zwariowałem, pieniądze rozdaję! - Bitocy zarabia na życie jako kuglarz na jarmarku w Bajtowej.
Zaprasza przechodniów do specyficznej zabawy. Na stoliku w rzędzie stoi kubków z numerami , pod niektórymi schowane są kauczukowe kulki. Jeśli grający dokładnie odgadnie, które to kubki, to dostaje wielkiego pluszowego misia. Bitocy odpłatnie udziela grającemu podpowiedzi. Za bajtogroszy Bitocy gotów jest zdradzić, jaka jest parzystość liczby kulek schowanych pod kubkami o numerach .
Bajtazar przyszedł na jarmark z Bajtyną - najładniejszą panną w całej Bajtowej. Bardzo chciałby wygrać dla niej misia. Nie zamierza przy tym narażać się na kompromitację i zgadywać, nie będąc pewnym odpowiedzi. Będzie płacił za podpowiedzi tak długo, aż zebrane informacje pozwolą mu ustalić z całą pewnością, pod którymi kubkami znajdują się kulki.
Znając ceny wszystkich możliwych podpowiedzi, zastanawia się teraz, ile maksymalnie będzie go to kosztować. Ściślej rzecz biorąc, chciałby znać najmniejszą taką liczbę , że istnieje strategia zadawania pytań, która niezależnie od odpowiedzi Bitocego pozwala na zlokalizowanie kulek za co najwyżej bajtogroszy.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę kubków. Po nim następuje opis kosztów zapytań o poszczególne przedziały. W -szym wierszu wejścia (dla ) znajduje się liczb całkowitych, oznaczających koszty poszczególnych podpowiedzi.
Koszt (, ) zapytania o przedział od -tego do -tego kubka włącznie pojawia się na wejściu jako -ta liczba w -szym wierszu.
Twój program powinien wypisać jedną liczbę całkowitą będącą maksymalnym kosztem ustalenia położenia kulek dla optymalnej strategii zadawania pytań.
Dla danych wejściowych:
5 1 2 3 4 5 4 3 2 1 3 4 5 2 1 5
poprawną odpowiedzią jest:
7
Autorzy zadania: Anna Zych, Jakub Pawlewicz.